//! ## 20. Valid Parentheses (easy, stack)
//! Given a string `s` containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.
//!
//! An input string is valid if:
//!
//! 1. Open brackets must be closed by the same type of brackets.
//! 2. Open brackets must be closed in the correct order.
//!
//! #### Example 1
//! ```txt
//! Input: s = "()"
//! Output: true
//! ```
//!
//! #### Example 2
//! ```txt
//! Input: s = "()[]{}"
//! Output: true
//! ```
//!
//! #### Example 3
//! ```txt
//! Input: s = "([)]"
//! Output: false
//! ```
//!
//! #### Example 4
//! ```txt
//! Input: s = "{[]}"
//! Output: true
//! ```
//!
//! #### Constraints
//! - `1 <= s.length <= 10e4`
//! - `s` consists of parentheses only '()[]{}'.
//! ### 知识点
//! - 括号配对问题适合使用 stack 数据结构

use std::collections::HashMap;

pub struct Solution;

impl Solution {
    /// #### 原理
    /// - 利用 stack 数据结构后入先出的原理, 实现括号配对
    /// - 使用 hashmap 保存括号的对应关系.
    /// #### 流程
    /// 使用 stack 数据结构, '(', '[', '{' 入栈,
    /// 遇到 '}', ']', ')' 出栈, 看是否匹配
    ///
    /// 最后 stack 为空说明是有效的
    /// #### 边界分析
    /// - 空字符串, 已包含
    /// #### 复杂度
    /// - 时间复杂度
    ///     - 只需要遍历一遍字符串, O(n)
    /// - 空间复杂度
    ///	    - stack 空间, O(n)
    pub fn solve(s: String) -> bool {
        let mut stack = vec![];
        let map: HashMap<char, char> = vec![('(', ')'), ('[', ']'), ('{', '}')]
            .into_iter()
            .collect();

        for c in s.chars() {
            match c {
                '(' | '[' | '{' => {
                    stack.push(c);
                }
                ')' | ']' | '}' => match stack.pop() {
                    Some(c_) => {
                        let &c_ = map.get(&c_).unwrap();
                        if c_ != c {
                            return false;
                        }
                    }
                    None => return false,
                },
                _ => {}
            }
        }
        // stack 为空说明是有效的
        stack.is_empty()
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test() {
        assert_eq!(Solution::solve(String::from("()")), true);
        assert_eq!(Solution::solve(String::from("()[]{}")), true);
        assert_eq!(Solution::solve(String::from("(]")), false);
        assert_eq!(Solution::solve(String::from("([)]")), false);
        assert_eq!(Solution::solve(String::from("{[]}")), true);
    }
}
